An Application Specific Integrated Circuit (“ASIC”) can be implemented in either a semi-custom gate array or a full-custom gate array. In a semi-custom gate array, embedded memory is implemented as blocks of fixed binary sized memory blocks or macro cells. In a binary sized macro cell the number of columns and rows are a multiple of a power of two. In a full custom gate array embedded memory is implemented with custom macro cells. Custom macro cells are designed using compilers that allow embedded memory to have a non-binary number of rows and columns.
The design of a semi-custom ASIC requires less effort but requires that embedded memory be implemented in fixed size binary macro cells. Many applications store non-binary width data structures in memory. Storing non-binary width structures in a fixed size binary width memory requires including more memory than necessary in the ASIC.
FIG. 1A illustrates a prior art binary macro cell 100 for storing a non-binary width data structure including sixteen non-binary (21-bit) entries. The 16 Mega (224) bit memory macro cell includes 215 (32K) logical rows. Each logical row is 29 (512) bits as 28 (256) bit logical rows would be insufficient to store sixteen 21-bit mapper entries (336 bits). With sixteen entries per logical row and 32K logical rows, the macro cell 100 can store 512K (219) entries. By storing sixteen entries per logical row, a logical row is indexed by the 15 most significant bits of a 19-bit pointer and an entry within the indexed logical row is identified by the lower 4-bits of the 19-bit pointer. Thus, a 15-bit base pointer can be stored to index a logical row and the 19-bit pointer can be computed by adding a 4-bit offset to the 15-bit base pointer. Memory for storing pointers to entries stored in the macro cell 100 is therefore reduced by storing 15-bit base pointers for blocks of 16 entries per logical row instead of storing a separate 19-bit pointer for each entry in the macro cell 100.
As shown, the macro cell 100 can store sixteen non-binary (21-bit width) entries in the first 336 bits of each 512-bit wide logical row. 10 Mega bits (32K×336 bits) of the 16 Mega bits memory are used to store the sixteen 21-bit wide entries and 6 Mega bits (32K×176 bits) of the 16 Mega bits memory block are not used.
Thus, almost thirty-five percent (6M/16M) of the 16M fixed size binary macro cell shown in FIG. 1A is not used when the binary macro cell stores a non-binary width data structure.